package com.mc.algorithm;

public class ReversePair {
	private int count=0;
    public int InversePairs(int [] array) {
		if(array.length==0)
            return 0;
        sort(0,array.length-1,array);
        return count;
    }
    public void sort(int low,int high,int[] a){
        if(low>=high)
            return;
        int mid = low+(high-low)/2;
        sort(low,mid,a);
        sort(mid+1,high,a);
      	count(low,mid,high,a);
    }
    public void count(int low,int mid,int high,int[] a){
        int i=mid;
        int j;
        while(i>=low){
			j=high;
            while(j>mid){
                if(a[i]>a[j]){
                   count+=j-mid;
                    break;
                }
                else
                	j--;               
            }
            if(j==mid)
                break;
            i--;
        }
        int[] temp = new int[a.length];
        for(int k = low;k<=high;k++)
            temp[k] = a[k];
        
        i=low;
        j=mid+1;
        for(int k = low;k<=high;k++){
            if(i>mid)a[k]=temp[j++];
            else if(j>high)a[k]=temp[i++];
            else if(temp[i]<=temp[j])a[k]=temp[i++];
            else
                a[k] = temp[j++];
        }
    }
    public static void main(String[] args) {
		ReversePair rp = new ReversePair();
		int res=rp.InversePairs(new int[]{3,2,1,4,0});
		System.out.println(res);
    }
}